package DynamicProgramming;//数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
//
// 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。 
//
// 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。 
//
// 
//
// 示例 1： 
//
// 
//输入：cost = [10, 15, 20]
//输出：15
//解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
// 
//
// 示例 2： 
//
// 
//输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
//输出：6
//解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
// 
//
// 
//
// 提示： 
//
// 
// cost 的长度范围是 [2, 1000]。 
// cost[i] 将会是一个整型数据，范围为 [0, 999] 。 
// 
// Related Topics 数组 动态规划 👍 713 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class minCostClimbingStairs {
    public int minCostClimbingStairs(int[] cost) {

        /**
         * 动态规划，题目要求得在当前台阶一次可以跳一阶或二阶
         * 跳二阶时即表示跳过中间得一阶，当到达一阶时要消耗当前阶得体力，跳过则不消耗
         * 所以某一阶得状态可以有前一阶到当前阶，也可由前二阶跳过中间一阶到当前阶
         * dp[i] 表示到当前阶所花费最小体力
         * dp[i] = Math.min(dp[i-1], dp[i-2] + cost[i])
         * 因为到达当前阶必定会消耗当前阶得体力，所以从前两阶种选择一个最小消耗体力开始
         * 而到达最后时要看，最后一阶得前两阶谁得最小体力
         * */
        int len = cost.length;
        int[] dp = new int[len];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];
        }
        //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
        return Math.min(dp[len - 1], dp[len - 2]);

    }
}
//leetcode submit region end(Prohibit modification and deletion)
